package 剑指offer;

import java.util.ArrayList;
import java.util.List;

public class Offer29_JZ19 {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        ArrayList<Integer> list = new ArrayList<>();
        boolean[][] visited = new boolean[rows][cols];
        dfs(matrix, visited, 0, 0, list);
        return list;
    }

    public void dfs(int[][] matrix, boolean[][] visited, int i, int j, ArrayList<Integer> list) {
        if (i<0 || i>=matrix.length || j<0 || j>=matrix[0].length || visited[i][j]) {
            return;
        }
        list.add(matrix[i][j]);
        visited[i][j] = true;
        if (j-1<0 || visited[i][j-1]) {
            dfs(matrix, visited, i-1, j, list);
        }
        // 右，下，左，上
        dfs(matrix, visited, i, j+1, list);
        dfs(matrix, visited, i+1, j, list);
        dfs(matrix, visited, i, j-1, list);
        dfs(matrix, visited, i-1, j, list);
    }
}
